package stack;

import java.util.Stack;

/**
 * @author yyz
 * @create 2024-01-03 19:29
 */
public class 中缀转后缀表达式 {
    private String infixToSuffix(String token) {
        Stack<Character> s = new Stack<>();
        StringBuilder sb = new StringBuilder(token.length());
        for (char c : token.toCharArray()) {
            switch (c) {
                case '+', '-', '*', '/' -> {
                    if (s.isEmpty()) {
                        s.push(c);
                    } else {
                        if (value(c) > value(s.peek())) {
                            s.push(c);
                        } else {
                            while (!s.isEmpty() && value(s.peek()) >= value(c)) {
                                sb.append(s.pop());
                            }
                            s.push(c);
                        }
                    }
                }
                case '(' -> s.push(c);
                case ')' -> {
                    while (!s.isEmpty() && s.peek() != '(') {
                        sb.append(s.pop());
                    }
                    s.pop();
                }
                default -> sb.append(c);
            }
        }
        while (!s.isEmpty()) {
            sb.append(s.pop());
        }
        return sb.toString();
    }

    private int value(char c) {
        return switch (c) {
            case '+', '-' -> 2;
            case '*', '/' -> 4;
            case '(', ')' -> 0;
            default -> throw new IllegalStateException("错误的运算符: " + c);
        };
    }

    public static void main(String[] args) {
        System.out.println(new 中缀转后缀表达式().infixToSuffix("a+b"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("a+b-c"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("a+b*c"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("a*b-c"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("(a+b)*c"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("(a+b*c-d)*e"));
        System.out.println(new 中缀转后缀表达式().infixToSuffix("a*(b+c)"));
    }
}
